/*
**算法思想**

 策略：贪心策略
 数组：
1.一个用来存城市是否经过的数组 Travel[]
2.二维数组用来存城市路径 City[][]
 函数：
Path 求路径
FindMin 找与当前城市相连通的城市中路径最短的城市 并需要利用 Travel数组确认城市是否已经走过
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct City_info
{
    int City_Map[10][10] ;
    char City_Name[10] = { 'A' , 'B' , 'C' , 'D' , 'E' , 'F' , 'G' , 'H' , 'I' , 'J' };
};

typedef struct City_info INFO;

void Info_Start(int Info[]);
void Travel( int City_Map[10][10] , char City_Name[]);
int Path( int City_Map[10][10] , char City_Name[] , int Travel_Info[] );
int Find_Next_City( int City_Map[10][10] ,  int Travel_Info[] );
void Start( int Data[][10]);
void initialization( int Data[][10] );
void Print(int data[][10],int row,int col);
void Rain();


//void Find_Next2_City( int City_Map[10][10] ,  int Travel_Info[] , int Root_City);
int Step_Path = 0;
int Step_Path_Pack = 0;
int Step_Node = 0;
int Step_Node_Pack = 0;
int Travel_Count = 0;
int Root_City = 10;
int Step_Info[10];
int Travel_Info[10];

void Start( int Data[][10])
{
    srand((unsigned) time(0)); //用时间做种，每次产生随机数不一样
    for( int i = 0; i < 10 ; i++)
    {
        for(int j = 0; j < 10 ; j++)
        {
            if(i == j) Data[i][j] = 0;
            else Data[i][j] = rand() % 101;
        }
    }
}

void Info_Start(int Info[])
{
    for( int i = 0; i < 10; i++)
    {
        Info[i] = 0;
    }
}

void Rain()
{
    char member[18] = {
            '0', '1', ' ', ' ', 'a', 'b', 'c', ' ', ' ', 'f', ' ', 'z', ' ', 'y', 'x', '@', '#', '&'
    };
    int i;
    int flag;
    for (int m = 0; m <= 100; m++) {
        if (m % 2 == 0) {
            for (i = 0; i <= 100; i++) {
                flag = rand() % 18;
                printf(" %c ", member[flag]);
                if (i % 2 == 0) printf(" ");
                if (i % 20 == 0) printf("\n");
            }
        }
    }
}

void initialization( int Data[][10] )
{
    for( int i = 0; i < 10 ; i++ )
    {
        for(int j = 0; j < 10 ; j++)
        {
            Data[i][j] = 0;
        }
    }
}

void Travel( int City_Map[10][10] , char City_Name[])
{
    Info_Start( Travel_Info );
    Info_Start( Step_Info );
    printf(" %c -> " , City_Name[Root_City]);
    Travel_Info[ Root_City ] = 1;
    Path( City_Map , City_Name , Travel_Info );
}

int Path( int City_Map[10][10] , char City_Name[] , int Travel_Info[] )
{
    int temp = Step_Path;//记录上一次所走的里程
    Step_Path = City_Map[Root_City][0];//假定城市A为离上一个城市最近的城市
    Step_Node = Root_City;//将Step_Node置为上一次经过的城市
    if(Step_Path == 0 )
        Step_Path = City_Map[Root_City][Root_City+1];
    Find_Next_City( City_Map , Travel_Info );
    Travel_Count ++;//旅行次数加一
    Travel_Info[ Step_Node ] = 1;//将该城市在旅行信息表中标记为走过
    printf(" %c -> ", City_Name[Step_Node]);
    Step_Path += temp;//对旅行所走过的路程进行累计
    if( Travel_Count < 9)//一共需要旅行十个城市
    {
        Root_City = Step_Node;//将这次所选择的下一个城市作为下一次选择根城市
        return Path(City_Map, City_Name, Travel_Info );
    }
    else
    {
        printf("OVER\n Travel is over\n");
        printf("The length of your travel is %d \n" , Step_Path );
    }
}

int Find_Next_City( int City_Map[10][10] ,  int Travel_Info[] )
{
    int Step_Count = 0;//记录步骤顺序
    for( int i = 0 ; i < 10 ; i++)//可能出现的BUG ： 碰到了最小的城市都去过了，没去过的城市都比出发城市大
    {
        if( City_Map[Root_City][ i ] <= Step_Path && City_Map[Root_City][ i ] != 0
            )//选择下一个城市的判断条件
        {
            if(Travel_Info[i] == 0)
            {
                Step_Path_Pack = Step_Path;
                Step_Path = City_Map[Root_City][i];//得到前往下一个城市的路程
                //printf("%d ",Step_Path);
                Step_Node_Pack = Step_Node;
                Step_Node = i;//得到下一个城市的名称
                //printf("%d\n",Step_Node);
            }
        }
    }
    if( Step_Node == Root_City ) {
        Step_Node = Step_Node_Pack;
        Step_Path = Step_Path_Pack;
    }
    //City_Map[Root_City][Step_Node] = 100;
}

void Print(int data[][10],int row,int col)
{
    printf("The result is :\n");
    for(int i = 0;i < row; i++)
    {
        for( int j = 0; j< col ; j++)
        {
            if( data[i][j] >= 100 )
                printf(" %d",data[i][j]);
            else if( data[i][j] >= 10 )
                printf(" %d ",data[i][j]);
            else
                printf(" %d  ",data[i][j]);
            if( j == col -1)
                printf("\n");
        }
    }
}

int main()
{
    INFO Ten_City;
    printf("I am initializating the city map:\n");
    initialization( Ten_City.City_Map );
    Rain();
    printf("I am choosing which city should we go:\n");
    Start( Ten_City.City_Map );
    printf("OK! This is the map of the city we will go:\n");
    Print( Ten_City.City_Map ,10,10);
    printf("There are the city you want travel: \n");
    for (int i = 0; i < 10 ; ++i) {
        if( i <= 8)
            printf(" %d : %c \n", i+1 ,Ten_City.City_Name[i]);
        else
            printf(" %d: %c \n", i+1 ,Ten_City.City_Name[i]);
    }//打印城市编号及城市名称；
    printf("Please enter the city you want begin:\n");
    int Key_Time ;
    for(  Key_Time = 0; Root_City > 9 && Key_Time < 3 ;Key_Time++)
    {
        int temp ;
        scanf("%d", &temp);
        Root_City = temp - 1;
        if ( Root_City > 9)
            printf("We don't have such a city in our map,please choose again\n");
    }
    if( Key_Time >= 3 || Root_City > 9)
        printf("You have to stay in your home instead of going anywhere\n");
    else
    {
        printf(" Travel begin :\n");
        Travel( Ten_City.City_Map, Ten_City.City_Name );
        for(int i = 0; i < 10 ; i++)
        {
            printf("%d",Travel_Info[i]);
        }
    }
    return 0;
}